package 剑指offer;

import java.util.*;

public class p40最小的k个数 {
    //排序
    public int[] getLeastNumbers1(int[] arr, int k) {
        Arrays.sort(arr);
        int[] res=new int[k];
        for (int i = 0; i <k; i++) {
            res[i]=arr[i];
        }
        return res;
    }

    //利用 最大堆,查找 最小数的 K个数
    public int[] getLeastNumbers2(int[] arr, int k) {
        if (arr.length<k || k==0) {
            return new int[]{};
        }

        // 默认是小根堆，实现大根堆需要重写一下比较器。
        //Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);


        Queue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });//优先级队列，默认创建的是小堆，但此处需要的是 大根堆

        for (int num:arr) {
            if (queue.size()<k) {
                queue.add(num);
                continue;
            }
            if (queue.size()==k && num<queue.peek()) {
                queue.poll();
                queue.add(num);
            }
        }
        //队列转成数组
        int[] res=new int[k];
        for (int i = 0; i <k; i++) {
            res[i]=queue.poll();
        }

        return res;
    }

    //利用 最大堆,查找 最小数的 K个数
    public int[] getLeastNumbers3(int[] arr, int k) {
        if (k==0) {
            return new int[0];
        }

        //利用优先级队列，创建大堆
        Queue<Integer> queue=new PriorityQueue<>(((o1, o2) -> o2-o1 ));

        for (int num:arr) {
            if (queue.size()<k) {
                queue.add(num);
            }else if(queue.peek()>num){
                //else if(queue.size()==k && queue.peek()>num){
                //堆中的元素个数 == k,就要判断堆顶元素与当前num的大小，num小于堆顶，将堆顶弹出，num进入
                queue.poll();
                queue.add(num);
            }
        }

        int[] res=new int[k];
        for (int i = 0; i <k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }

    public static void main(String[] args) {
        Queue<Integer> queue=new PriorityQueue<>(((o1, o2) -> o2-o1));


        System.out.println(queue.peek()>2);//当队列中没有元素时，队首元素为 null,null和数值不能比较！！！
    }

}
